import java.util.*;

public class Maptest {


    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret = new ArrayList();
            Arrays.sort(nums);
            for(int i=0;i<nums.length; ){
                int left = i+1;
                int right = nums.length-1;
                int target = -nums[i];
                if(nums[i]>0){
                    break;
                }
                while(left<right){
                    if(nums[left]+nums[right]>target){
                        right--;
                    }
                    else if(nums[left]+nums[right]<target){
                        left++;
                    }
                    else{
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                        left++;
                        right--;
                        while(nums[left]==nums[left-1]&&(left<right)){
                            left++;
                        }
                        while(nums[right]==nums[right+1]&&(right>left)){
                            right--;
                        }

                    }
                }
                i++;
                while(i<nums.length && nums[i]==nums[i-1]){
                    i++;
                }
            }
            return ret;
        }
    }
}
